#include "stack_queue.h"


// 先实现节点类的构造函数和析构函数
listNode::listNode() // 无参构造
{
    next = NULL;
}

listNode::listNode(int nodeData, listNode *succ)
{
    data = nodeData;
    next = succ;
}

// 再实现链栈类MyStack的成员函数
MyStack::MyStack() // 构造函数,(由于这个链栈没有头结点,似乎只需要初始化一下stackSize即可)?
{
    topNode = NULL;
    stackSize = 0;
}

MyStack::~MyStack() // 析构函数,删除所有节点
{
    listNode *p = topNode;
    while (p != NULL)
    {
        listNode *temp = p;
        p = p->next;
        delete temp;
    }
    topNode = NULL;
}

bool MyStack::push(const int &a) // 把a入栈,成功返回true,失败返回false
{
    listNode *newnode = new listNode(a, topNode);
    if (newnode == NULL)
    {
        return false;
    }
    topNode = newnode;
    stackSize++;
    return true;
}

bool MyStack::pop(int &item) // 出栈,成功返回true,失败返回false,出栈元素放在item
{
    if (stackSize == 0)
    {
        return false;
    }
    else
    {
        item = topNode->data;
        listNode *temp = topNode;
        topNode = topNode->next;
        delete temp;
        stackSize--;
        return true;
    }
}

bool MyStack::getTop(int &item) // 获取栈顶,成功返回true,失败返回false,栈顶元素放在item
{
    if (stackSize == 0)
    {
        return false;
    }
    else
    {
        item = topNode->data;
        return true;
    }
}

void MyStack::printStack() // 按照栈顶到栈底的顺序输出栈内所有元素
{
    listNode *p = topNode;

    while (p != NULL)
    {
        if (p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
    }
}

bool MyStack::empty()
{
    if (stackSize == 0)
    {
        return true;
    }
    return false;
}

// 实现顺序队列的成员函数
MyQueue::MyQueue(const int &capacity) // 队列初始化,MyQueue(const int& capacity),创建队列,容量为capacity
{
    queue = (int *)malloc(capacity * sizeof(int));
    this->capacity = capacity;
    front = 0; // 让front和rear都指向0
    rear = 0;
}

MyQueue::~MyQueue()
{
    free(queue);
    queue = NULL;
}

bool MyQueue::enQueue(const int &e) // 入队
{
    if ((rear + 1) % capacity == front) // 队满
    {
        return false;
    }
    queue[rear] = e; // 队尾入队
    rear = (rear + 1) % capacity;
    return true;
}

bool MyQueue::deQueue(int &e) // 出队,出队元素放在e
{
    if (front == rear) // 对空
    {
        return false;
    }
    e = queue[front];
    front = (front + 1) % capacity;
    return true;
}

bool MyQueue::getFront(int &e) // 获取队头元素,放在e
{
    if (front == rear) // 对空
    {
        return false;
    }
    e = queue[front];
    return true;
}

bool MyQueue::isFull() // 判断是否队满
{
    if ((rear + 1) % capacity == front)
    {
        return true;
    }
    return false;
}

void MyQueue::printQueue()
{
    int cursor = front;

    while (cursor != rear)
    {
        if ((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}

// 基于MyStack进行扩展改进(如改变栈内元素类型、对符号进行合理数值映射)，实现中缀表达式转后缀表达式和表达式求值，支持小括号、加减乘除四则运算,一位正整数(0-9)运算,不涉及多位数、负数及小数
int precedence(char op) // 判断运算符的优先级
{
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    return 0;
}

bool isopreartor(char ch) // 判断是不是运算符
{
    return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}

bool trueExpression(string s) // 判断表达式是否合法
{
    MyStack parentheses;             // 用于检查括号的平衡
    bool lastCharWasOperator = true; // 用于检查上一个字符是否是运算符，初始化为true表示表达式不能以运算符开头
    bool hasOperand = false;         // 用于检查是否有至少一个操作数

    for (int i = 0; i < s.length(); i++)
    {
        char c = s[i];

        // 忽略空格
        if (isspace(c))
        {
            continue;
        }

        if (c == '(')
        {
            // 如果遇到左括号，压入栈中
            parentheses.push(c);
            lastCharWasOperator = true; // 左括号后面应跟操作数或另一个左括号
        }
        else if (c == ')')
        {
            // 如果遇到右括号，检查是否有匹配的左括号
            if (parentheses.empty())
            {
                return false; // 没有匹配的左括号
            }
            int a;
            parentheses.pop(a);
            lastCharWasOperator = false; // 右括号后面不能跟操作数
        }
        else if (isdigit(c))
        {
            // 如果是数字，合法
            hasOperand = true;
            lastCharWasOperator = false; // 数字后面不能跟另一个数字（中间应该有运算符）
        }
        else if (c == '+' || c == '-' || c == '*' || c == '/')
        {
            // 如果是运算符，检查其合法性
            if (lastCharWasOperator)
            {
                return false; // 如果前一个字符是运算符或左括号，表达式不合法
            }
            lastCharWasOperator = true;
        }
        else
        {
            // 如果遇到非数字、运算符和括号的字符，表达式非法
            return false;
        }
    }

    // 遍历完成后，检查括号是否匹配并且最后一个字符不是运算符
    if (!parentheses.empty() || lastCharWasOperator || !hasOperand)
    {
        return false;
    }

    return true;
}

bool postfixExpression(const string &s, string &result) // 中缀表达式转后缀表达式,转化成功返回true, 后缀表达式放在result中,表达式错误返回false, 错误字符串Expression is wrong!放在result中
{
    if (trueExpression(s) == false) // 如果不是一个正确的表达式,直接输出错误
    {
        result = "Expression is wrong!";
        return false;
    }
    // 表达式正确,开始中缀转后缀
    MyStack opstack;
    result = "";

    for (int i = 0; i < s.size(); i++) // 遍历表达式
    {
        char ch = s[i];
        if (ch >= '0' && ch <= '9') // 数字直接加到答案中
        {
            result = result + ch;
        }
        else if (ch == '(') // 左括号直接入栈
        {
            opstack.push(ch);
        }
        else if (ch == ')') // 右括号一直弹,直到遇到左括号(左括号也要弹出)
        {
            while (!opstack.empty())
            {
                int temp;
                opstack.pop(temp);
                if (temp == '(')
                {
                    break;
                }
                result = result + (char)temp;
            }
        }
        else if (isopreartor(ch)) // 如果是运算符,保证栈的严格单调
        {
            int temp;
            opstack.getTop(temp);
            while (precedence(temp) >= precedence(ch) && !opstack.empty() && (char)temp != '(')
            {
                opstack.pop(temp);
                result = result + (char)temp;
                opstack.getTop(temp);
            }
            opstack.push(ch);
        }
        else if (ch == ' ') // 如果是空格,跳过
        {
            continue;
        }
    }

    // 最后运算符中还有一些符号,全部加到result中
    int top;
    while (opstack.pop(top))
    {
        result = result + (char)top;
    }
    return true;
}

// 表达式求值函数
bool expressionVal(const string &expr, int &result)
{
    MyStack stack; // 使用给定的栈
    int operand1, operand2;
    string pos; // 先把中缀表达式转化为后缀表达式
    postfixExpression(expr, pos);
    // 遍历后缀表达式中的每一个字符
    for (char ch : pos)
    {
        if (isdigit(ch))
        {
            // 如果是数字，压入栈
            int num = ch - '0'; // 字符转数字
            stack.push(num);
        }
        else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
        {
            // 如果是操作符，从栈中弹出两个操作数
            if (!stack.pop(operand2) || !stack.pop(operand1))
            {
                result=0;
                return false; // 如果无法弹出操作数，表达式非法
            }

            int resultTemp;
            // 进行相应的操作
            switch (ch)
            {
            case '+':
                resultTemp = operand1 + operand2;
                break;
            case '-':
                resultTemp = operand1 - operand2;
                break;
            case '*':
                resultTemp = operand1 * operand2;
                break;
            case '/':
                if (operand2 == 0)
                {
                    result=0;
                    return false; // 除零错误
                }
                resultTemp = operand1 / operand2;
                break;
            default:
                return false; // 如果出现未知操作符，表达式非法
            }

            // 将结果压回栈中
            stack.push(resultTemp);
        }
        else if (ch == ' ')
        {
            // 跳过空格
            continue;
        }
        else
        {
            result=0;
            return false; // 如果遇到非法字符，表达式非法
        }
    }

    // 计算结束后，栈中应该只剩一个元素，即结果
    if (!stack.pop(result) || !stack.empty())
    {
        result=0;
        return false; // 如果栈中有多余元素或为空，表达式非法
    }

    return true; // 计算成功
}

// 基于MyQueue，实现输出杨辉三角
void yanghui(const int &n)
{
    MyQueue q(n * (n + 3)); // 队列的大小足够存储前 n 行的元素
    q.enQueue(1);q.enQueue(1);
    int s=0;
    for(int i=1;i<=n;i++)
    {
        q.enQueue(0);
        for(int j=1;j<=i+2;j++)
        {
            int t;
            q.deQueue(t);
            q.enQueue(s+t);
            s=t;
            if(j<i+1)
            {
                cout << s << ",";
            }
            if(j==i+1)
            {
                cout << s;
            }
        }
        cout << endl;
    }
}
